package kaiao.dynamic;

import java.util.Arrays;

public class 不同路径 {

	public static void main(String[] args) {

	}

	//
	public int uniquePaths(int m, int n) {

		/**
		 * 1.找到状态关联
		 * 不同路径到达dp[m][n] 的方式 dp[m - 1][n] + dp[m][n - 1]
		 * 2.初始化数组
		 * dp[1 ~ m][0] = 1
		 * dp[0][1 ~ n] = 1
		 */

		// 初始化
		int[][] dp = new int[m + 1][n + 1];

		for (int i = 1; i < m + 1; i++) dp[m][0] = 1;
		for (int i = 1; i < n + 1; i++) dp[0][n] = 1;

		for (int i = 1; i < m + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}

		return dp[m][n];
	}
}
